'''
MOLS算法实现
解的选择、评估和更新逻辑
'''
import copy
import random
import time

import Globals
import Utils


# 重置染色体
def reset_chromosome(chromosome):
    chromosome.routes.clear()
    chromosome.f = [0 for _ in range(Globals.FUNC_NUM)]


# 重置路径
def reset_route(route):
    route.customers.clear()
    route.travel_dist = 0.0
    route.travel_time = 0.0
    route.wait_time = 0.0
    route.delay_time = 0.0
    route.delivery_capacity = 0.0
    route.pick_up_capacity = 0.0


# 初始化路径
def init_route(chromosome):
    # 假设reset_chromosome函数已正确初始化染色体
    reset_chromosome(chromosome)
    cust_index = list(range(1, Globals.customer_num + 1))  # 客户索引列表

    # 当还有未服务的客户时，尝试创建新的路线
    while cust_index:
        new_route = Globals.Route()
        new_route.customers.append(0)  # 新路径从配送中心开始
        last = 0  # last代表上一个客户，初始从配送中心开始
        arrival_time, wait_time, d_capacity, p_capacity, m_capacity = 0.0, 0.0, 0.0, 0.0, 0.0

        # 服务过的客户
        severed_cust = set()
        # 临时客户列表
        temp_cust_index = cust_index[:]

        while temp_cust_index:
            # 随机选择客户
            next_cust = random.choice(temp_cust_index)
            # 客户已经服务过则跳过
            if next_cust in severed_cust:
                continue
            temp_cust_index.remove(next_cust)
            severed_cust.add(next_cust)
            # 时间约束
            arrival_time += Globals.peer_time[last][next_cust]
            wait_time = max(0, Globals.customer[next_cust].begin_time - arrival_time)

            # 容量约束
            d_capacity += Globals.customer[next_cust].delivery_demand
            p_capacity += Globals.customer[next_cust].pick_up_demand

            # 最大载荷 tmp_max
            if last == 0:
                tmp_max = Globals.customer[next_cust].delivery_demand
            else:
                tmp_max = max(d_capacity, m_capacity + Globals.customer[next_cust].delivery_demand)

            # 判断约束条件
            if (
                    p_capacity <= Globals.max_capacity and d_capacity <= Globals.max_capacity and tmp_max <= Globals.max_capacity and
                    arrival_time <= Globals.customer[next_cust].end_time + Globals.max_delay_time[next_cust] and
                    arrival_time + wait_time + Globals.customer[next_cust].server_time + Globals.peer_time[next_cust][
                0] <=
                    Globals.customer[0].end_time):
                # 满足约束条件，加入路线
                arrival_time += wait_time + Globals.customer[next_cust].server_time
                m_capacity = tmp_max
                new_route.customers.append(next_cust)
                last = next_cust
                cust_index.remove(next_cust)
            else:
                # 不满足约束条件，回滚修改
                arrival_time -= Globals.peer_time[last][next_cust]
                d_capacity -= Globals.customer[next_cust].delivery_demand
                p_capacity -= Globals.customer[next_cust].pick_up_demand

        # 完成路线的创建，如果路线中有客户被服务
        if len(new_route.customers) > 1:
            new_route.customers.append(0)  # 路线结束，返回配送中心
            Utils.get_distance(new_route)
            Utils.get_time(new_route)
            chromosome.routes.append(new_route)

        # 如果没有剩余客户，结束路线创建
        if not cust_index:
            break

    # 打印生成路线结果
    # for i, route in enumerate(chromosome.routes):
    #     print(f"Route {i + 1}: {' -> '.join(map(str, route.customers))}")
    #     print(f"Distance: {route.travel_dist}, Time: {route.travel_time}\n")

    # 打印约束条件检查结果
    # print(f"约束条件检查结果：{Utils.check_both(chromosome)}")


# 初始化参数,生成权重向量和计算每个权重向量的邻域
def init_para():
    # 初始化已生成权重向量的数量为0
    Globals.pop_num = 0
    for i in range(Globals.H + 1):
        Globals.array[i] = i
    for i in range(Globals.FUNC_NUM):
        Globals.temp[i] = 0
    # 生成权重向量
    # dfs(0, 0)
    generate_weight_vectors()

    # 计算邻域
    for i in range(Globals.N):
        Utils.get_neighbor(i)
        Utils.get_neighbor(i)


def generate_weight_vectors():
    # 对于5个目标函数的情况，我们需要找到所有可能的权重组合，使得这些权重之和为H
    # 这里使用了四层循环来遍历所有可能的组合。每层循环对应一个目标函数的权重。
    # 由于我们已知总和为H，因此可以在每次迭代中动态减少下一个权重的可能最大值，以保证总和不超过H。
    for i in range(Globals.H + 1):  # 第一个权重i从0到H
        for j in range(Globals.H + 1 - i):  # 第二个权重j的最大值取决于i的值
            for k in range(Globals.H + 1 - i - j):  # 第三个权重k的最大值取决于i和j的值
                for l in range(Globals.H + 1 - i - j - k):  # 第四个权重l的最大值取决于i、j和k的值
                    Globals.pop_num += 1
                    # 基于前四个权重计算第五个权重m，确保权重之和为H
                    m = Globals.H - i - j - k - l
                    # 生成权重向量，并通过除以H将其归一化到[0,1]区间
                    vector = [i / Globals.H, j / Globals.H, k / Globals.H, l / Globals.H, m / Globals.H]
                    # 将生成的归一化权重向量添加到列表中
                    Globals.lambda_v.append(vector)


# 递归生成权重向量
# 通过深度优先搜索遍历所有可能的权重组合,当权重的总和等于H时，将当前组合作为一个权重向量保存到lamda中
def dfs(index, sum):
    if index == Globals.FUNC_NUM:
        if sum == Globals.H:
            for j in range(Globals.FUNC_NUM):
                Globals.lambda_v[Globals.pop_num][j] = Globals.temp[j] / (Globals.H * 1.0)
            Globals.pop_num += 1
        return
    if sum > Globals.H:
        return
    for i in range(Globals.H + 1):
        Globals.temp[index] = Globals.array[i]
        dfs(index + 1, sum + Globals.array[i])


def init_pop():
    for i in range(Globals.FUNC_NUM):
        Globals.extreme[i].f[i] = Globals.INF

    chromo = Globals.Chromosome()

    for i in range(Globals.N):
        reset_chromosome(chromo)
        while True:
            # 初始化生成路径
            init_route(chromo)
            Utils.get_f(chromo)
            result = Utils.check_vehicle_num(chromo) and Utils.check_both(chromo)
            if result:
                break
        init_chromo = copy.deepcopy(chromo)
        Globals.chromosome.append(init_chromo)
        update_EP(init_chromo)

    Utils.out_N()

    init_para()


# 更新当前的有效前沿
def update_EP(new_chromosome):
    copy_chromosome = copy.deepcopy(new_chromosome)
    flag = False
    # 为新染色体计算盒子分数
    Utils.get_box(copy_chromosome)
    # print()
    # print(f"lambda:{r_lambda}")
    # print("新染色体的值：")
    # Utils.print_chromo_info(copy_chromosome)
    # 如果当前EP集合为空，则直接添加新染色体到EP集合中，并更新极值解
    if len(Globals.EP) == 0:
        # print(f"EP集合为空,添加染色体解决方案到EP中")
        # 更新极值解
        update_extreme(copy_chromosome)
        Globals.EP.append(copy_chromosome)
        # print("当前EP的值：")
        # for chromo in Globals.EP:
        #     print(chromo)
        #     Utils.print_chromo_info(chromo)
    # 如果EP不为空
    else:
        # print(f"update_EP：当前EP不为空")
        # 遍历EP集合中的每个染色体
        for chrom in Globals.EP:
            # EP中存在某个染色体比新染色体更好或者与新染色体相等，则直接返回，不对EP进行更新
            # 如果新染色体在某一个目标上至少比EP中的一个方案更好，则进行后续更新
            # 否则说明新染色体在任意一项目标都不比当前档案的解更好，就没必要进行更新
            if Utils.is_better(chrom, copy_chromosome) or Utils.is_equal(chrom, copy_chromosome):
                # print("新染色体比EP的解决方案都差")
                return
        # print(f"新染色体是否是极值解：{is_extreme(copy_chromosome)}")
        # 检查新染色体是否是极值解
        if Utils.is_extreme(copy_chromosome):
            # 更新EP中所有被新染色体支配的解，并添加新染色体到EP集合中
            update_extreme(copy_chromosome)
            #  将当前EP中比新染色体差的解决方案移除
            Globals.EP = [chrom for chrom in Globals.EP if not Utils.is_better(copy_chromosome, chrom)]
            Globals.EP.append(copy_chromosome)
            # print(f"新染色体是极值解，添加新染色体进入EP中：")
            # print("当前EP的值：")
            # for chromo in Globals.EP:
            #     print(chromo)
            #     Utils.print_chromo_info(chromo)
        # 如果新染色体不是极值解
        else:
            # print("新染色体不是极值解")
            # 但能支配EP中的某些解，则移除这些被支配的解
            updated_EP = [chrom for chrom in Globals.EP if not Utils.is_better(copy_chromosome, chrom)]
            if len(updated_EP) < len(Globals.EP):  # 如果列表长度变短了，说明有染色体被移除了
                flag = True
            Globals.EP = updated_EP

            if flag:
                # print("新染色体不是极值解，新染色体能支配某些EP的解，添加进入EP中")
                # 添加新染色体到EP集合中
                Globals.EP.append(copy_chromosome)
            # 如果没有找到被新染色体支配的解
            else:
                # print("新染色体能不能支配某些EP的解")
                is_insert = True
                # 但新染色体在某些盒子分数上优于EP中的解
                for chrom in Globals.EP:
                    if Utils.is_equal_box(chrom, copy_chromosome) or Utils.is_better_box(chrom, copy_chromosome):
                        is_insert = False
                        break
                # print(f"新染色体在某些盒子分数上优于EP的解：{is_insert}")
                # 也将新染色体添加到EP中
                if is_insert:
                    # print("新染色体不是极值解，新染色体不能支配某些EP的解，但在某些盒子分数上优于EP的解，添加进入EP中")
                    Globals.EP.append(copy_chromosome)


# 如果新染色体在某个目标上比当前记录的极值解更好，就更新这个极值解为新染色体
def preserve_extreme(chrome, index):
    if Globals.extreme[index].f[index] - chrome.f[index] > 0.000001:
        Globals.extreme[index] = chrome
    # else:
    #     if is_better(chrome, Globals.extreme[index]):
    #         Globals.extreme[index] = chrome


# 遍历所有目标，使用preserve_extreme来更新每个目标上的极值解。
def update_extreme(new_chromosome):
    for i in range(Globals.FUNC_NUM):
        preserve_extreme(new_chromosome, i)


def update_best(new_chromosome):
    copy_chromosome = copy.deepcopy(new_chromosome)
    if len(Globals.total_best) == 0:
        Globals.total_best.append(copy_chromosome)
    else:
        # 检查是否有更优或相等的染色体存在
        for chromosome in Globals.total_best:
            if Utils.is_better(chromosome, copy_chromosome) or Utils.is_equal(chromosome, copy_chromosome):
                return False

        # 删除被新染色体支配的染色体
        Globals.total_best = [chrom for chrom in Globals.total_best if not Utils.is_better(copy_chromosome, chrom)]

        # 添加新染色体
        Globals.total_best.append(copy_chromosome)
    return True


def process(stop_time):
    start = time.time()
    init_pop()
    new_chromo = Globals.Chromosome()
    while True:
        for i in range(Globals.N):
            # 寻找极值
            Utils.get_max_min()
            while True:
                index_1 = random.randint(0, Globals.T - 1)
                index_2 = random.randint(0, Globals.T - 1)
                if index_1 != index_2:
                    break
            reset_chromosome(new_chromo)
            # 随机选择邻域中的两个解
            chromo_1 = Globals.chromosome[Globals.B[i][index_1]]
            chromo_2 = Globals.chromosome[Globals.B[i][index_2]]
            # 交叉生成新解
            crossover(chromo_1, chromo_2, new_chromo, Globals.lambda_v[i])

            # 局部搜索
            local_search(new_chromo, Globals.lambda_v[i])

            finish = time.time()
            if (finish - start) > stop_time:
                return

            # 更新邻域
            for j in range(Globals.T):
                index = Globals.B[i][j]
                lambda_para = Globals.lambda_v[index]
                new_chromo.w_f = Utils.get_wf(new_chromo, lambda_para)
                Globals.chromosome[index].w_f = Utils.get_wf(Globals.chromosome[index], lambda_para)
                if new_chromo.w_f < Globals.chromosome[index].w_f:
                    Globals.chromosome[index] = copy.deepcopy(new_chromo)


def crossover(chromo_1, chromo_2, new_chromo, r_lambda):
    is_used = [False] * Globals.MAX
    RP = [0] * Globals.MAX
    reset_chromosome(new_chromo)
    temp_route = Globals.Route()

    # 从父代染色体1中随机选则n条路线
    ind_1 = random.randint(0, len(chromo_1.routes) - 1)
    # print("染色体1选中的路线：", end="")
    for i in range(ind_1):
        index = random.randint(0, len(chromo_1.routes) - 1)
        while is_used[index]:
            # 选择之前没选过的路线
            index = random.randint(0, len(chromo_1.routes) - 1)
        # print(index, end=" ")
        # 将路线添加进新染色体中
        new_chromo.routes.append(chromo_1.routes[index])
        is_used[index] = True
    # print()

    # print("染色体2选中的路线：", end="")
    for i in range(len(chromo_2.routes)):
        flag = False
        for cust in range(1, len(chromo_2.routes[i].customers) - 1):
            for j in range(len(new_chromo.routes)):
                route = new_chromo.routes[j]
                if cust in route.customers:
                    flag = True
                    break
            if flag:
                break
        if not flag:
            # print(i, end=" ")
            new_chromo.routes.append(chromo_2.routes[i])
    # print()

    # 下面处理未被添加进新染色体中的客户
    for i in range(1, Globals.customer_num + 1):
        is_used[i] = False

    for route in new_chromo.routes:
        for j in range(1, len(route.customers) - 1):
            is_used[route.customers[j]] = True

    # 生成一个随机排列数列RP
    Utils.get_RP(RP, Globals.customer_num)

    # 最长旅行时间的路径
    max_travel_time = 0
    max_travel_route = None
    for route in new_chromo.routes:
        if route.travel_time > max_travel_time:
            max_travel_time = route.travel_time
            max_travel_route = route
    if max_travel_route is None:
        return False

    if r_lambda[0] != 1:
        # 优化其他四个目标
        for i in range(Globals.customer_num):
            # 这里是随机选择客户，目的是避免局部最优解，提高解的多样性
            if not is_used[RP[i] + 1]:
                insert_customer(new_chromo, r_lambda, RP[i] + 1, max_travel_time)
    else:
        # 优化车辆数量
        for i in range(Globals.customer_num):
            if not is_used[RP[i] + 1]:
                route = None
                for route in new_chromo.routes:
                    if check_feasible_place(route, RP[i] + 1):
                        Utils.get_time(route)
                        Utils.get_distance(route)
                        break
                if route == new_chromo.routes[len(new_chromo.routes) - 1]:
                    temp_route = Globals.Route()
                    temp_route.customers.append(0)
                    temp_route.customers.append(RP[i] + 1)
                    temp_route.customers.append(0)
                    Utils.get_time(temp_route)
                    Utils.get_distance(temp_route)
                    new_chromo.routes.append(temp_route)

    for route in new_chromo.routes:
        Utils.get_time(route)
        Utils.get_distance(route)
    Utils.get_f(new_chromo)
    return True


def insert_customer(chromosome, r_lambda, cust, max_travel_time):
    # 计算未插入客户时的总距离
    total_dist = sum(route.travel_dist for route in chromosome.routes)

    # print(f"total_dist：{total_dist}")
    # 存储无法插入的客户
    uninserted_customers = []
    temp_route = Globals.Route()
    feasible = False
    min_delta = 99999999
    inserted_route = None
    c_pos, min_c_pos, r_pos = 0, 0, None
    # print(f"每次插入前路径数量：{len(chromosome.routes)}")
    for r in chromosome.routes:
        now_wait = 0
        now_delay = 0
        for route in chromosome.routes:
            if r != route:
                now_wait += route.wait_time
                now_delay += route.delay_time

        r_num = len(chromosome.routes)
        result = Utils.check_best_pos(cust, r, r_lambda, total_dist, now_wait, now_delay, r_num)
        # print(f"插入结果：插入路线：{r.customers}，{result[0]}，{result[1]}，{result[2]}")

        if result[0]:
            feasible = True
            delta = result[2]
            if min_delta > delta:
                min_delta = delta
                min_c_pos = result[1]
                inserted_route = r
        # else:
        #     print(f"无法插入的路线：{' -> '.join(map(str, r.customers))}")

    # print(f"delta：{min_delta}")

    if not feasible or (r_lambda[2] == 1 and max_travel_time < min_delta):
        # 无法插入客户，为其重新创建一条路线
        # print(f"当前客户{cust}没有合适的位置，重新创建一条路径")
        uninserted_customers.append(cust)
        reset_route(temp_route)
        temp_route.customers.append(0)
        temp_route.customers.append(cust)
        temp_route.customers.append(0)
        Utils.get_time(temp_route)
        Utils.get_distance(temp_route)
        chromosome.routes.append(temp_route)
    else:
        # 将客户插入到现有路线的最佳位置
        # print(f"当前客户:{cust}有合适插入位置")
        # print("插入路线如下：")
        # print(f"{chromosome.routes.index(inserted_route) + 1}：{' -> '.join(map(str, inserted_route.customers))}")
        inserted_route.customers.insert(min_c_pos, cust)
        # print("插入后路线如下：")
        # print(f"{chromosome.routes.index(inserted_route) + 1}：{' -> '.join(map(str, inserted_route.customers))}")
        Utils.get_time(inserted_route)
        Utils.get_distance(inserted_route)

    # print(f"插入后的结果：{Utils.check_both(chromosome)}")
    # total_dist2 = sum(route.travel_dist for route in chromosome.routes)
    # print(f"添加后的总距离：{total_dist2}")

    # print(f"每次插入后路径数量：{len(chromosome.routes)}")
    # print(f"未被插入的客户：{uninserted_customers}")
    # for cust in uninserted_customers:
    #     create_new_route(chromosome,cust,r_lambda)


def check_feasible_place(route, cust):
    # print(route.customers)
    # print(cust)
    # time代表到达前一个客户点的累计时间
    time, capacity = 0, 0
    Utils.get_time(route)
    Utils.get_capacity(route, 0)

    for i in range(1, len(route.customers) - 1):
        capacity += Globals.customer[route.customers[i]].delivery_demand
    #  加上新添用户的送货量
    capacity += Globals.customer[cust].delivery_demand
    # 判断添加客户后路线的最大送货量是否超过货车最大送货量
    if capacity > Globals.max_capacity:
        # print("check_feasible_place结果：超重")
        return False

    for i in range(1, len(route.customers) - 1):
        pre_cust = route.customers[i - 1]
        cur_cust = route.customers[i]
        next_cust = route.customers[i + 1]

        # print(f"cur_cust:{cur_cust}")
        # print(f"begin_time1:{Globals.customer[cur_cust].begin_time}")

        # 容量约束
        # 配送中心出发到客户的最大载荷
        if Globals.M_minus[0][i] + Globals.customer[cust].delivery_demand > Globals.max_capacity:
            # print("check_feasible_place结果：超重1")
            return False
        # 离开客户到到达配送中心的最大载荷
        if Globals.M_plus[0][i - 1] + Globals.customer[cust].pick_up_demand > Globals.max_capacity:
            # print("check_feasible_place结果：超重2")
            return False

        # 时间约束
        # 假设用户插入到第i个客户之前
        # 计算到达新客户的时间
        tmp_time = time + Globals.peer_time[pre_cust][cust]
        # 检查是否晚于插入客户的最晚服务时间
        if tmp_time > Globals.customer[cust].end_time + Globals.max_delay_time[cust]:
            # 当前插入客户不能插在这个位置
            # 将总时间加上第i-1个客户和第i个客户之间的时间
            time += Globals.peer_time[pre_cust][cur_cust]
            # 如果总时间小于客户i的最早服务时间
            if time < Globals.customer[cur_cust].begin_time:
                # 将总时间设置为客户i的最早服务时间（因为要等到它开始能服务，会产生等待时间）
                time = Globals.customer[cur_cust].begin_time
            # 加上第i个客户的服务时间
            time += Globals.customer[cur_cust].server_time
            # 插入当前客户不满足时间窗要求，直接跳到下一个客户
            continue

        # 如果到达时间小于插入客户的最早服务时间
        if tmp_time < Globals.customer[cust].begin_time:
            # 将到达时间设置为插入客户的最早服务时间（因为要等到它开始能服务，会产生等待时间）
            tmp_time = Globals.customer[cust].begin_time

        # 这里到达客户i的时间等于到达插入客户的时间加上服务时间再加上路程的时间
        tmp_time += Globals.customer[cust].server_time + Globals.peer_time[cust][cur_cust]
        # print(f"temp_time:{tmp_time}")
        # print(f"cur_cust:a_time:{Globals.a_time[cur_cust]}")

        # 如果插入客户后到达i的时间满足时间窗要求
        if (tmp_time <= Globals.a_time[cur_cust]) or (tmp_time <= Globals.customer[cur_cust].begin_time):
            # print("insert")
            # 将客户插入当前路线
            route.customers.insert(i, cust)
            # 重新计算路线的行驶距离和时间
            Utils.get_distance(route)
            Utils.get_time(route)
            return True

        # 如果上面都没满足代表客户不能插入到客户i之前
        time += Globals.peer_time[pre_cust][cur_cust]
        if time < Globals.customer[cur_cust].begin_time:
            time = Globals.customer[cur_cust].begin_time
        time += Globals.customer[cur_cust].server_time

    # 最后是插入到返回配送中心的前面
    index = len(route.customers) - 1
    depot = route.customers[index]
    pre_cust = route.customers[index - 1]
    # 配送中心出发到客户的最大载荷
    if Globals.M_minus[0][depot] + Globals.customer[cust].delivery_demand > Globals.max_capacity:
        return False
    # 离开客户到到达配送中心的最大载荷
    if Globals.M_plus[0][pre_cust] + Globals.customer[cust].pick_up_demand > Globals.max_capacity:
        return False
    time += Globals.peer_time[pre_cust][cust]
    if time > Globals.customer[cust].end_time + Globals.max_delay_time[cust]:
        return False
    if time < Globals.customer[cust].begin_time:
        time = Globals.customer[cust].begin_time
    time += Globals.customer[cust].server_time + Globals.peer_time[cust][depot]
    if time <= Globals.customer[depot].end_time:
        # 将客户插入当前路线
        route.customers.insert(index, cust)
        # 重新计算路线的行驶距离和时间
        Utils.get_distance(route)
        Utils.get_time(route)
        return True

    return False


def local_search(chromosome, r_lambda):
    # 优化车辆数量
    if r_lambda[0] == 1:
        while True:
            min_num = 999999
            route_index = -1
            # 寻找客户数量最少的路线
            for i, route in enumerate(chromosome.routes):
                if min_num > len(route.customers):
                    min_num = len(route.customers)
                    route_index = i
            # if route_index == -1:
            #     break
            # 如果无法进一步优化，退出循环
            # print('route_index', route_index)
            # print(f"Route {route_index}: {' -> '.join(map(str, chromosome.routes[route_index].customers))}")
            result = route_number(chromosome, route_index)
            # print(f"route_number result:{result}")
            if result:
                continue
            else:
                break

        # 重新计算路线的行驶距离和时间
        for route in chromosome.routes:
            Utils.get_distance(route)
            Utils.get_time(route)

        # 重新计算染色体的目标函数值并更新解集
        Utils.get_f(chromosome)
        result = Utils.check_vehicle_num(chromosome)
        if not result:
            return False
        update_EP(chromosome)
        return True
    # 优化其他四个目标
    else:
        count = 0
        best = copy.deepcopy(chromosome)
        # print("local_search")
        # print(f"chromosome:{chromosome} best:{best}")
        while count < 10:
            result = localsearch_k(chromosome, r_lambda, best, -1)
            if not result:
                continue
            else:
                chromosome, best = result
            # if result is not None:
            #     chromosome, best = result
            # else:
            #     print(f"result：{result} count:{count} r_lambda:{r_lambda}")
            #     print(chromosome)
            #     for route in chromosome.routes:
            #         print(route.customers)
            #     Utils.print_chromo_info(chromosome)
            count += 1

        # 重新计算路线的距离和时间
        for route in chromosome.routes:
            Utils.get_distance(route)
            Utils.get_time(route)

        # 重新计算染色体的目标函数值
        Utils.get_f(chromosome)
        return True
        # 更新EP（这个需要根据实际情况来实现，可能涉及到非支配排序等操作）
        # update_EP(chromosome)


def route_number(chromosome, route_index):
    # if route_index < 0 or route_index > len(chromosome.routes):
    #     print(f"index:{route_index}")
    #     for route in chromosome.routes:
    #         print(route.customers)
    route = chromosome.routes[route_index]
    i = 1  # 从第一个客户开始
    j = 0
    while i < len(route.customers) - 1:  # 避免遍历到最后一个元素（配送中心）
        Utils.get_time(route)
        # 时间约束检查
        # 判断下一个客户是否是回到配送中心
        pre_customer = route.customers[i - 1]
        current_customer = route.customers[i]
        next_customer = route.customers[i + 1]

        # print(f"遍历{i}")
        # print(f"当前客户{current_customer}")

        if (next_customer == 0 and Globals.l_time[pre_customer] + Globals.peer_time[pre_customer][
            next_customer] < Globals.customer[0].end_time) or \
                (next_customer != 0 and Globals.l_time[pre_customer] + Globals.peer_time[pre_customer][
                    next_customer] < Globals.customer[next_customer].end_time + Globals.max_delay_time[next_customer]):

            # print(f"当前客户{current_customer}满足时间要求")
            # 尝试找到其他路线插入当前客户
            for j in range(len(chromosome.routes)):
                if j != route_index and check_feasible_place(chromosome.routes[j], current_customer):
                    # print(f"del {i}")
                    # 找到合适位置，从当前路径删除客户
                    del route.customers[i]
                    break
            if j == len(chromosome.routes) - 1:
                # print(f"当前客户{current_customer}满足时间要求，但没有合适位置")
                return False  # 如果没有找到可行的位置，说明无法优化，则返回 False
        else:
            # 不满足时间约束
            return False
        if j == len(chromosome.routes) - 1:  # 如果没有执行删除操作，移动到下一个客户
            i += 1

    if len(route.customers) == 2:  # 如果路线中只剩下起始和终止点
        del chromosome.routes[route_index]
        return True

    return False


def localsearch_k(chromosome, r_lambda, best, index):
    # print("localsearch_k")
    # print(f"chromosome:{chromosome}")
    # print(f"best:{best}")

    removed_customers = []
    temp_route = Globals.Route()
    max_travel_time = 0
    removed_customers.clear()
    if r_lambda[2] != 1:
        route_index = random.randint(0, len(chromosome.routes) - 1)
    else:
        # 最长旅行时间的路径
        max_travel_time = 0
        max_travel_route = None
        for route in chromosome.routes:
            if route.travel_time > max_travel_time:
                max_travel_time = route.travel_time
                max_travel_route = route
        if max_travel_route is None:
            return False
        route_index = chromosome.routes.index(max_travel_route)
    route = chromosome.routes[route_index]

    # print(f"被选中的路径{route_index + 1}：{' -> '.join(map(str, route.customers))}")
    # 根据概率随机选择N1，N2，N3三个算子
    p = random.random()

    if p < 1.0 / 3:
        N1_algorithm(chromosome, route, removed_customers, route_index)
    elif 1.0 / 3 <= p < 2.0 / 3:
        N2_algorithm(chromosome, route, removed_customers, route_index)
    else:
        N3_algorithm(chromosome, r_lambda, route_index, max_travel_time)

    # print(f"执行完算子前的约束检查：{Utils.check_both(chromosome)}")

    for cust in removed_customers:
        insert_customer(chromosome, r_lambda, cust, max_travel_time)

    # print(f"执行完算子后的约束检查：{Utils.check_both(chromosome)}")
    # print("-------------------------------------------------------")
    Utils.get_f(chromosome)
    result = Utils.check_vehicle_num(chromosome)
    if not result:
        return False

    chrome_wf = Utils.get_wf(chromosome, r_lambda)
    best_wf = Utils.get_wf(best, r_lambda)
    if best_wf > chrome_wf:
        best = copy.deepcopy(chromosome)
    elif best_wf < chrome_wf:
        chromosome = copy.deepcopy(best)

    # print(f"执行完localsearch_k后：{chromosome} {best}")

    update_EP(chromosome)

    if chromosome is None or best is None:
        print(f"chromosome:{chromosome}")
        print(f"best:{best}")

    return chromosome, best


def N1_algorithm(chromosome, route, removed_customers, route_index):
    # print("执行N1算子")
    # 从路线中随机选择一个客户进行移除
    if len(route.customers) <= 3:
        cust_index = 1
    else:
        cust_index = random.randint(1, len(route.customers) - 2)

    if 1 <= cust_index <= len(route.customers) - 2:
        cust = route.customers.pop(cust_index)  # 移除客户
    else:
        return
        # cust = route.customers.pop(cust_index)  # 移除客户
    removed_customers.append(cust)  # 插入到要被插入的客户列表

    # print(f"被移除客户列表：{removed_customers}")
    # print(f"移除客户后的路径{route_index + 1}：{' -> '.join(map(str, route.customers))}")
    # 移除客户后只剩配送中心，这条路线删除
    if len(route.customers) == 2:
        chromosome.routes.pop(route_index)
    else:
        # 检查移除客户后当前路线是否满足时间窗约束
        if Utils.check_time(route):
            Utils.get_distance(route)
            Utils.get_time(route)
        else:
            # print("*************************************")
            # print("有分裂路线")
            # print("*************************************")
            Utils.split_route(chromosome, route_index)
            # print(f"分裂后约束检查结果：{Utils.check_both(chromosome)}")


def N2_algorithm(chromosome, route, removed_customers, route_index):
    # print("执行N2算子")
    # 随机确定要从路线中移除的客户数量
    if len(route.customers) <= 3:
        count = 1
    else:
        count = random.randint(1, len(route.customers) - 2)

    # 随机移除指定数量的客户
    for _ in range(count):
        if len(route.customers) <= 3:
            cust_index = 1
        else:
            cust_index = random.randint(1, len(route.customers) - 2)

        if 1 <= cust_index <= len(route.customers) - 2:
            cust = route.customers.pop(cust_index)  # 移除客户
        else:
            return
        removed_customers.append(cust)

    # print(f"被移除客户列表：{removed_customers}")
    # print(f"移除客户后的路径{route_index + 1}：{' -> '.join(map(str, route.customers))}")
    # 移除客户后只剩配送中心，这条路线删除
    if len(route.customers) == 2:
        # print("路径没有客户，删除路径")
        chromosome.routes.pop(route_index)
    else:
        if Utils.check_time(route):
            Utils.get_time(route)
            Utils.get_distance(route)
        if not Utils.check_time(route):
            # print("*************************************")
            # print("有分裂路线")
            # print("*************************************")
            Utils.split_route(chromosome, route_index)
            # print(f"分裂后约束检查结果：{Utils.check_both(chromosome)}")


def N3_algorithm(chromosome, r_lambda, r_index, now_time):
    selected_route = chromosome.routes[r_index]
    c_index = random.randint(0, len(selected_route.customers) - 2)
    Utils.get_time(selected_route)
    Utils.get_distance(selected_route)
    dist, now_wait, now_delay = 0, 0, 0
    feasible = False
    min_delta = float('inf')
    exchange_r_index = 0
    min_c_pos = 0

    for i, route in enumerate(chromosome.routes):
        if i != r_index:
            dist = sum(r.travel_dist for j, r in enumerate(chromosome.routes) if j != r_index and j != i)
            now_wait = sum(r.wait_time for j, r in enumerate(chromosome.routes) if j != r_index and j != i)
            now_delay = sum(r.delay_time for j, r in enumerate(chromosome.routes) if j != r_index and j != i)
            route_num = len(chromosome.routes)

            result = Utils.check_best_pos_for_exchange(selected_route, c_index, route, r_lambda, route_num, dist,
                                                       now_time,
                                                       now_wait,
                                                       now_delay)

            if result[0]:
                feasible = True
                delta = result[2]
                if min_delta > delta:
                    min_delta = delta
                    min_c_pos = result[1]
                    exchange_r_index = i

    # print(f"feasible:{feasible}")

    if (not feasible) or (r_lambda[2] == 1 and min_delta > now_time):
        divide_route(chromosome, r_index, c_index)
    else:
        exchange_subsequences(chromosome, r_index, exchange_r_index, c_index, min_c_pos)


# 执行N3算子后将给定的路线在指定客户处分割成两条新路线。
def divide_route(chromosome, r_index, c_index):
    # 要分裂的路线
    divided_route = chromosome.routes[r_index]
    # 分裂的两天新路线
    new_route_1 = Globals.Route()
    new_route_2 = Globals.Route()
    # 将路线从选中客户开始分裂成两条新路线
    for i in range(0, c_index + 1):
        cust = divided_route.customers[i]
        new_route_1.customers.append(cust)
    new_route_1.customers.append(0)

    new_route_2.customers.append(0)
    for i in range(c_index + 1, len(divided_route.customers)):
        cust = divided_route.customers[i]
        new_route_2.customers.append(cust)

    # 更新新路线的信息
    Utils.get_time(new_route_1)
    Utils.get_distance(new_route_1)
    Utils.get_time(new_route_2)
    Utils.get_distance(new_route_2)

    # 从染色体中移除原路线，并添加新分割出的路线
    del chromosome.routes[r_index]
    if len(new_route_1.customers) > 2:  # 确保路线中有超过一个客户
        chromosome.routes.append(new_route_1)
    if len(new_route_2.customers) > 2:  # 确保路线中有超过一个客户
        chromosome.routes.append(new_route_2)


def exchange_subsequences(chromosome, r_index1, r_index2, c_index1, c_index2):
    # 获取两条路线
    route1 = chromosome.routes[r_index1]
    route2 = chromosome.routes[r_index2]
    c_index2 = route2.customers.index(c_index2)
    # print(f"route1:{route1.customers}")
    # print(f"route2:{route2.customers}")
    # print(f"c_index1:{c_index1}  c_index2:{c_index2}")

    # 交换两条路线的子序列
    new_customers_1 = []
    new_customers_2 = []
    # 序列1
    for i in range(0, c_index1 + 1):
        new_customers_1.append(route1.customers[i])
    for i in range(c_index2 + 1, len(route2.customers)):
        new_customers_1.append(route2.customers[i])
    # 序列2
    for i in range(0, c_index2 + 1):
        new_customers_2.append(route2.customers[i])
    for i in range(c_index1 + 1, len(route1.customers)):
        new_customers_2.append(route1.customers[i])

    # 更新客户列表
    route1.customers = new_customers_1
    route2.customers = new_customers_2

    # 更新交换后的路线信息
    Utils.get_time(route1)
    Utils.get_distance(route1)
    Utils.get_time(route2)
    Utils.get_distance(route2)

    # 如果交换后的路线只包含配送中心，移除该路线
    if len(route1.customers) == 2:
        del chromosome.routes[r_index1]
    if len(route2.customers) == 2:
        del chromosome.routes[r_index2]
